#pragma once
#include "BitSet.h"
#include <time.h> 

namespace sqy 
{
    struct HashBKDR
    {
        size_t operator()(const string& key)
        {
            size_t val = 0;
            for(auto& e : key)
            {
                val *= 131;
                val += e;
            }
            return val;
        }
    };
    struct HashAP
    {
        size_t operator()(const string& key)
        {
            size_t hash = 0;
            for(size_t i = 0; i < key.size(); i++)
            {
                if((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash<<11) ^ key[i] ^ (hash >> 5)));
                }
            }
            return hash;
        }
    };
    struct DJBHash
    {
        ssize_t operator()(const string& key)
        {
            size_t hash = 5381;
            for(auto e : key)
            {
                hash += (hash << 5) + e;
            }
            return hash;
        }
    };
    template<size_t N,
        class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = DJBHash>
    class BloomFilter
    {
    public:
        void Set(const K& key)
        {
            size_t hash1 = Hash1()(key) % (_ratio*N);
            _bits.set(hash1);

            size_t hash2 = Hash2()(key) % (_ratio*N);
            _bits.set(hash2);

            size_t hash3 = Hash3()(key) % (_ratio*N);
            _bits.set(hash3);
        }
        bool test(const K& key)
        {
            size_t hash1 = Hash1()(key) % (_ratio*N);
            if(!_bits.test(hash1))
            {
                return false;
            }
            
            size_t hash2 = Hash2()(key) % (_ratio*N);

            if(!_bits.test(hash2))
            {
                return false;
            }
            size_t hash3 = Hash3()(key) % (_ratio*N);
            if(!_bits.test(hash3))
            {
                return false;
            }
            return true;//可能存在误判
        }

    private:
        const static size_t _ratio = 5;
        sqy::bit_set<_ratio * N> _bits;
    };
   // void BloomFilterTest()
   // {
   //     string arr[] = { "苹果","葡萄", "阿里", "美团", "字节", "香蕉", "苹果", "苹果", "葡萄", "苹果", "香蕉", "苹果", "香蕉", "苹果", "葡萄" };
   //     BloomFilter<10>bf;
   //     for(auto& e : arr)
   //     {
   //         bf.Set(e);
   //     }
   //     for(auto& e : arr)
   //     {
   //         cout<< bf.test(e) << endl;
   //     }

   //     cout<< endl<< endl;
   //     string arr1[] = { "苹果 ","葡萄", "阿里 112", "美团", "字节", "香蕉21", "苹果221", "苹果", "葡萄22223", "苹果", "香1221蕉", "苹果", "香蕉", "苹果", "葡萄" };
   //     for(auto& e : arr1)
   //     {
   //         cout<< e << ":" << bf.test(e) << endl;
   //     }
   // }
    void TestBloomFilter2()
	{
		srand(time(0));
		const size_t N = 10000;
		BloomFilter<N> bf;
		cout << sizeof(bf) << endl;

		std::vector<std::string> v1;
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	
		for (size_t i = 0; i < N; ++i)
		{
			v1.push_back(url + std::to_string(1234 + i));
		}
	
		for (auto& str : v1)
		{
			bf.Set(str);
		}

		// 相似
		std::vector<std::string> v2;
		for (size_t i = 0; i < N; ++i)
		{
			std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html";
			url += std::to_string(rand() + i);
			v2.push_back(url);
		}

		size_t n2 = 0;
		for (auto& str : v2)
		{
			if (bf.test(str))
			{
				++n2;
			}
		}
		cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

		std::vector<std::string> v3;
		for (size_t i = 0; i < N; ++i)
		{
			string url = "zhihu.com";
			url += std::to_string(rand()+i);
			v3.push_back(url);
		}
	
		size_t n3 = 0;
		for (auto& str : v3)
		{
			if (bf.test(str))
			{
				++n3;
			}
		}
		cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
	}
}
